题目:
假设银行有K个窗口提供服务,窗口前设一条黄线,所有顾客按到达时间在黄线后排成一条长龙。当有窗口空闲时,下一位顾客即去该窗口处理事务。当有多个窗口可选择时,假设顾客总是选择编号最小的窗口。
本题要求输出前来等待服务的N位顾客的平均等待时间、最长等待时间、最后完成时间,并且统计每个窗口服务了多少名顾客。
输入格式:
输入第1行给出正整数N(≤1000),为顾客总人数;随后N行,每行给出一位顾客的到达时间T和事务处理时间P,并且假设输入数据已经按到达时间先后排好了顺序;最后一行给出正整数K(≤10),为开设的营业窗口数。这里假设每位顾客事务被处理的最长时间为60分钟。
输出格式:
在第一行中输出平均等待时间(输出到小数点后1位)、最长等待时间、最后完成时间,之间用1个空格分隔,行末不能有多余空格。
在第二行中按编号递增顺序输出每个窗口服务了多少名顾客,数字之间用1个空格分隔,行末不能有多余空格。
输入样例:
1 2 3 4 5 6 7 8 9 10 11
| 9 0 20 1 15 1 61 2 10 10 5 10 3 30 18 31 25 31 2 3
|
输出样例:
思路
依题意,我么可以每次处理一个顾客,按编号从小到大看哪一个窗口可以直接为该顾客提供服务,并同时计算需要等待的窗口的等待时长,取等待时间最短的作为预备窗口,如果最后没有能直接使用的窗口,则将预备窗口提供给该顾客使用。按上述模拟过程,代码如下。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
| #include <bits/stdc++.h>
using namespace std;
const int maxn=1100; const int Inf=0x3f3f3f3f;
int N,K;
struct Person { int arrive; int spend; }P[maxn];
Person windows[11]; int waitsum,waitmax,waitend; int num[11];
int main() { cin>>N; for(int i=0;i<N;i++) { cin>>P[i].arrive>>P[i].spend; P[i].spend=min(60,P[i].spend); } cin>>K; for(int i=0;i<N;i++) { int j; int wait=Inf,choice=0; for(j=1;j<=K;j++) { Person w=windows[j]; if(w.arrive+w.spend<=P[i].arrive) { windows[j]=P[i]; num[j]++; break; } else { int tmp=w.arrive+w.spend-P[i].arrive; if(tmp<wait) { wait=tmp; choice=j; } } } if(j>K) { waitsum+=wait; windows[choice]={P[i].arrive+wait,P[i].spend}; num[choice]++; waitmax=max(wait,waitmax); } } for(int i=1;i<=K;i++) { waitend=max(waitend,windows[i].arrive+windows[i].spend); } double waitaver=waitsum/(double)N; printf("%.1lf %d %d\n",waitaver,waitmax,waitend); for(int i=1;i<=K;i++) { if(i>1) putchar(' '); printf("%d",num[i]); } }
|